#pragma once
//AVL树的节点结构
using std::cout;
using std::endl;
#include <assert.h>

template<class K,class V>
class AVLTreeNode
{
public:
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;

	//存放数据的pair
	std::pair<K, V> _kv;
	//平衡因子
	int _bf;

	AVLTreeNode(const std::pair<K, V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_bf(0)
	{}
};

template<class K,class V>
class AVLTree
{
public:
	typedef AVLTreeNode<K,V> Node;
	bool Insert(const std::pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}
		//先去找空位置
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				//找着了就插入失败
				return false;
			}
		}
		//现在找到了应该插入的位置 创建一个新的节点
		cur = new Node(kv);

		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//插入完成 调整平衡因子  然后查看是否需要对树进行旋转操作
		while (parent)
		{
			//插入到了左树 平衡因子--
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else //插入到了右树 平衡因子++
			{
				parent->_bf++;
			}

			//平衡因子的判断 查看是否需要进行旋转
			if (parent->_bf == 0)
			{
				//插入使得树平衡了 不需要任何调整
				break;
			}
			else if (abs(parent->_bf) == 1)
			{
				//插入使得 以parent为根的树不平衡了 但需要看后续影响 判断是否需要旋转
				parent = parent->_parent;
				cur = cur->_parent;
			}
			else if (abs(parent->_bf) == 2)
			{
				//parent所在的子树已经不平衡了 需要做旋转处理

				if (parent->_bf == 2 && cur->_bf==1 )
				{
					//右侧本来就比左侧高， 而且插入的位置是右侧的右树
					//处理方案是将cur当成新的根节点，将cur的左树给老的根节点做右树
					//老根成为cur的左树
					RotateLeft(parent);//左旋转
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					//左侧本来就比右边高，而且插入的位置是左侧的左树。
					//处理方案是将cur当成新的根节点，将cur的右树给老的根结点做左树
					//老根成为cur的右树
					RotateRight(parent);//右旋转
				}
				else if( parent->_bf== -2 && cur->_bf==1)
				{
					RtotateLefttoRight(parent);
				}
				else if (parent->_bf == 2 && cur->_bf ==-1)
				{
					RtotateRighttoLeft(parent);
				}
				else
				{
					assert(false);
				}
				break;
			}
			else
			{
				assert(false);
			}

			return true;
		}
	}
	void RotateLeft(Node* parent)
	{
		Node* newparent = parent->_right;
		Node* given = newparent->_left;
		if (given)
		{
			given->_parent = parent;
		}
		//parent成为newparent的左树
		newparent->_left = parent;
		
		//因为还要修改_parent指针 所以保存一下 parent的_parent
		Node* pparent = parent->_parent;
		parent->_parent = newparent;

		//修改parent的_parent指针的指向
		if (parent == _root)
		{
			_root = newparent;
			newparent->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = newparent;
			}
			else
			{
				pparent->_right = newparent;
			}
		}
		newparent->_parent = pparent;
		newparent->_bf = parent->_bf = 0;

	}
	
	void RotateRight(Node* parent)
	{
		Node* newparent = parent->_left;
		Node* given = newparent->_right;
		if (given)
		{
			given->_parent = parent;
		}
		//parent成为newparent的左树
		newparent->_right = parent;

		//因为还要修改_parent指针 所以保存一下 parent的_parent
		Node* pparent = parent->_parent;
		parent->_parent = newparent;

		//修改pparent的左右孩子指针 和newparent的_parent指针的指向
		if (parent == _root)
		{
			_root = newparent;
			newparent->_parent = nullptr;
		}
		else
		{
			if (pparent->_left == parent)
			{
				pparent->_left = newparent;
			}
			else
			{
				pparent->_right = newparent;
			}
			newparent->_parent = pparent;
		}
		newparent->_bf = parent->_bf=0;

	}
	//插入位置在较高右子树的左侧
	void RtotateRighttoLeft(Node* parent)
	{
		//先对右子树 进行右旋 使得右子树的右侧高
		//再对parent位置进行左旋
		Node* firstRtotate = parent->_right;
		Node* newparent = firstRtotate->_left;
		int bf = newparent->_bf;
		RotateLeft(firstRtotate);
		RotateRight(parent);
		newparent->_bf = 0;

		//根据 newparent的起始_bf 确定情况
		//情况一 新节点插入到了 newparent的右子树
		if (bf == 1)
		{
				//				parent										newparent
				//		XXXX			firstRtotate		-->			parent     firstRtotate
				//					newparent        XXXX			XXX    NULL		new		XXX
				//				NULL      new		  
			parent->_bf = -1;
			firstRtotate->_bf = 0;

		}
		else if (bf == -1)
		{
			//情况二 新节点插入到了 newparent的左子树
			//				parent											newparent
			//		XXXX			firstRtotate			-->		parent			firstRtotate
			//					newparent        XXXX			XXXX	new		 NULL		  XXX
			//				 new		NULL		  
			firstRtotate->_bf = 1;
			parent->_bf = 0;
		}
		else if (bf == 0)
		{
			//新插入的节点 就是newparent
			//				parent 
			//		NULL			firstRtotate		
			//					newparent        
			firstRtotate->_bf = 0;
			parent->_bf = 0;

		}
		else
		{
			assert(false);
		}


	}
	//插入位置在较高左子树的右侧
	void RtotateLefttoRight(Node* parent)
	{
		Node* firstRtotate = parent->_left;  
		Node* newparent = firstRtotate->_right;
		int bf = newparent->_bf;

		RotateLeft(parent->_left);
		RotateRight(parent);

		newparent->_bf = 0;

		if (bf == 1)
		{
			
			parent->_bf = 0;
			firstRtotate->_bf = -1;
		}
		else if (bf == -1)
		{
			
			parent->_bf = 1;
			firstRtotate->_bf = 0;
		}
		else if (bf == 0)
		{
			
			parent->_bf = 0;
			firstRtotate->_bf = 0;
		}
		else
		{
			assert(false);
		}

	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}
private:
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftHT = Height(root->_left);
		int rightHT = Height(root->_right);
		int diff = rightHT - leftHT;

		if (diff != root->_bf)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}

		return abs(diff) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}

	int Height(Node* root)
	{
		if (root == nullptr)
			return 0;

		return max(Height(root->_left), Height(root->_right)) + 1;
	}

private:
	Node* _root = nullptr;
};
